The present invention relates to modem telecommunications in general, and more particularly to NEXT cancellation for modem pools.
Near-end cross talk (NEXT) is defined as the cross talk interference between the receiving path and the transmitting path of different transceivers that make use of wiring that share the same cable. The NEXT effect in a cable depends on the number of interfering lines, and increases as the bandwidth that the signals occupy increases. In a modem pool environment where streams of data are distributed to many lines within a single cable, the NEXT that the receivers need to overcome is mainly generated by the transmissions that the modem pool itself generates. Since such a system has access to the transmitted information for a plurality of modems, such information may be used to cancel the interference that leaks into the receivers, thus increasing the noise floor of each receiver.
In classic NEXT cancellation, a transmitter transmitting via one wire or wire grouping (e.g., twisted pair) affects the receiver receiving via another wire or wire grouping. A hybrid circuit separates the received signal from the transmitted interfering signal, but since the hybrid cannot completely separate the transmit path from the receive path, some of the transmitted signal leaks into the receiver and becomes an interfering signal. A canceller then filters out the effect of the interfering signal, resulting in a xe2x80x9ccleanedxe2x80x9d received signal. For a single modem, this problem may be addressed using classic echo cancellation techniques. In a modem pool environment where several modems transmits via a shared cable, the canceller for each receiver must take into account all the interfering transmitters. Thus, in order to cancel the NFM resulting from several modems in addition to each modem""s echo, one approach might to apply echo canceling techniques to each transmitting modem/receiving modem pair. However, such a solution would be relatively complex to implement, since the number of filters required would equal the square of the number of modems in the pool. A system implementing such a solution is described in U.S. Pat. No. 5,970,088.
There are two types of echo cancellation solutions: static and adaptive. In static echo cancellation, the echo canceling filter is adjusted during a learning phase, and the adjusted filter is then applied at steady state. In adaptive echo cancellation, the effect of each interferer is be studied over time using an adaptive filter which continually adjusts the signal to be cancelled out in accordance with changing line conditions in order to achieve optimal cancellation. One well-known adaptation method is the least mean squares (LMS) adaptive filter in which the xe2x80x9ccleanedxe2x80x9d signal is multiplied by a function of the interfering signal and is integrated over time, resulting in only the xe2x80x9cnon-cleanedxe2x80x9d part of the interfering signal remaining. This remaining signal represents the remaining energy of interference from a single transmitter. Both static and adaptive filters are estimates of the transfer function that a transmitter passed on the way to becoming an interferer.
Many static and adaptive echo canceling algorithms employ Finite Impulse Response (FIR) filters as the echo canceling filter. For a single NEXT canceller employing a FIR filter with N taps in the time domain, computing each output sample of a transmitted signal through the FIR filter requires approximately N multiplications and N additions. In a modem pool environment of M modems where any given receiver may be affected by a number of interfering transmitters, as well as by its own echo, up to M finite impulse response (FIR) filters may be required for each modem in order to cancel the NEXT from all interferers. The maximum number of arithmetic operations required for computing all output samples at a given time would therefore be of the order of Nxc2x7Mxc2x7M=Nxc2x7M2.
It is well known that time-domain filtering may be alternatively implemented in the frequency domain for a single modem. In this technique, the coefficients of a FIR filter are transformed to the frequency domain using techniques such as Fast Fourier Transform (FFT), thereby generating frequency domain coefficients. A stream of incoming time samples is divided into blocks. Each block of time samples is then modified, such as by zero padding the block or by concatenating some samples from a previous block to the current block. These modified blocks of samples are transformed to the frequency domain using techniques such as Fast Fourier Transform (FFT), thereby generating blocks of frequency samples. Each block of frequency samples is then multiplied coordinate-wise with the frequency domain coefficients, and the results are transformed back into the time domain using techniques such as inverse FFT to generate a second sequence of blocks of time domain samples. These time domain samples are then processed, such as by considering only certain samples from each block, or by overlapping and adding adjacent blocks, to ultimately arrive at a sequence of samples which represents the same sequence that would have been encountered were the original stream of incoming samples convolved with the FIR filter coefficients. A detailed description of this technique can be found in J. G. Proakis and D. G. Manolakis, xe2x80x9cDigital Signal Processing Principles, Algoritbms, and Applications, 2nd Edition,xe2x80x9d Macmillan Publishing Co., 1992, pp. 703-709, where two well known variants of block overlapping, xe2x80x9coverlap addxe2x80x9d and xe2x80x9coverlap save,xe2x80x9d are presented.
Computing N output samples for a single FIR of N taps would then require the following computations: 2 FFTs of length N (or 2N, if zero padding is applied) for transferring to the frequency domain and back to the time domain, and N complex multiplications for effecting the filter in the frequency domain. The complexity of each FFT operation, as expressed in terms of the number of multiplication and addition operations, is on the order of Nlog(N), and the complexity of effecting the filter in the frequency domain is N. Thus, the total complexity for computing N output samples is on the order of Nlog(N)+N, resulting in a total complexity per output sample of log(N)+1.
The use of frequency domain techniques for NEXT canceling is described in U.S. Pat. No. 5,887,032. However, the system described in U.S. Pat. No. 5,887,032 is a DMT system in which frequency domain techniques are applied on a modem by modem basis. No mention is made of a specific application in a modem pool environment, and the techniques described would be applied in exactly the same manner for one modem as they would be for M modems. Moreover, the NEXT cancellation method described by U.S. Pat. No. 5,887,032 is disadvantageous in several respects which are now described.
In the DMT NEXT cancellation system a cyclic prefix is added to each signal block prior to its transmission. For example, if a signal block has a length of 512 bytes, and the cyclic prefix has a length of 32 bytes, the transmitted signals will comprise blocks having a length of 544 bytes, only 512 bytes of which contain information symbols, with the remaining bytes considered a redundancy to be removed at the receiver. Typically, the processing of the received signal for DMT systems is done by:
1. Converting the received signal from analog to digital (A/D converter).
2. Applying an optimized filter known as a Time Domain Equalizer (TEQ) to find an optimal frame (e.g., of 512 bytes out of the 544 bytes in the preceding example) in which the effects of Inter Symbol Interference (ISI) and Inter Channel Interference (ICI) are minimized.
3. After finding the optimal frame, removing the cyclic prefix, leaving only the signal samples in the frame.
4. Transforming the signal samples to the frequency domain.
5. Applying the NEXT cancellation algorithm, including multiplying the data transmission coefficients (which are given in the frequency domain in DMT systems) by the complex coefficients of an adaptive Filter.
6. Combining the NEXT effects from several filters.
7. Subtracting the combined NEXT effect from the received signal to produce a clean signal.
This system bas the following disadvantages:
1. It attempts to reduce the NEXT effects only for portions of the received signal frames (e.g., 512 bytes of every 544 bytes). Thus, such a system cannot be applied to time-based systems employing CAP/QAM or PAM modulation, as they require NEXT cancellation for the whole stream of received samples, and not only for selected portions.
2. It does not take into account that in DMT systems the TEQ filter if optimized for the received far-end signal and not for the NEXT signal. Moreover, a frame which is chosen with respect to a far-end signal may not be optimized for the NEXT signals, and the estimation of the NEXT may therefore suffer from the well known ISI and ICI which are characteristic for non optimized frame selection.
The present invention seeks to provide NEXT cancellation for modem pools by employing frequency domain techniques that may significantly reduce the number of computations over time-domain techniques. The use of such frequency-domain techniques is not known in a modem pool environment such as in the modem pool of M modems described above. One possible reason for this is that the cutoff point between time domain and frequency domain techniques (i.e., the point where using frequency domain techniques becomes beneficial) is commonly believed to be at approximately N=30 taps. For FIR filters with less than 30 taps, time domain techniques are much simpler and require less arithmetic operations. Only where relatively long filters are used is there a noticeable gain when applying frequency domain techniques. However, in the modem pool environment of M modems described above, transforming the transmitted signals from the time domain to the frequency domain is done only once per modem, and transforming back from the frequency domain to the time domain is done once for each receiver. While effecting the filter in the frequency domain is done for each transmitting modem/receiving modem pair, thus requiring M2 filters, this operation requires only N complex multiplications per filter. In mathematical terms, the number of FFT operations to be performed grows linearly in relation to M, while the number of multiplications grows in relation to the square of M. Thus, the maximum number of arithmetic operations per time unit required in order to cancel the NEXT from all interferers for each of the M modems would be on the order of (Mlog(N)+M2).
For example, in a modem pool comprising 30 HDSL modems with a sampling rate of 1 MHz, in order to cancel all 30 NEXT interferers for each modem with a 16 tap FIR as an estimation of each NEXT impulse response, conventional techniques would require approximately 16*900 arithmetic operations for every output sample every 1 xcexcsec, or 14,000 MIPS (14*109 arithmetic operations each second). In contrast, the present invention reduces the number of arithmetic operations to approximately 1,000 operations every 1 xcexcsec, or about 1,000 MIPS. Even taking into account that the 1,000 operations required are complex number operations, there still remains a significant difference from prior art approaches. If the number of taps for the FIR filters is doubled to 32, then the complexity of conventional techniques would grow to 28,000 MIPS, while the present invention will require only a slight increase in complexity of about 30 MIPS. As mentioned above, the cutoff point for a single FIR is at about 30 taps. In the above example it may be seen that for a modem pool of 30 modems there is a significant advantage to implementing the FIRs with the aid of the frequency domain techniques of the present invention even for FIRs of 16 taps. The advantage is even more significant for 30 taps, which is the cutoff point for a single FIR.
In one aspect of the present invention NEXT cancellation is provided in a modem pool having a plurality of modems, where each modem has at least one FIR filter, each FIR filter for filtering signals from a transmitting one of the modems, each modem transmitting a signal having a plurality of contiguous signal blocks. A method is provided including providing a frequency response vector per FIR filter, for each corresponding one of the transmitted signal blocks for each of the modems adapting the length of the signal block to equal the length of the frequency response vector, transforming the adapted signal block into the frequency domain, thereby generating a frequency-domain signal vector, for each of the modems and its at least one FIR filter multiplying the frequency response vector of the FIR filter by a corresponding one of the frequency-domain signal vectors, thereby generating a filtered frequency-domain signal vector, adding the filtered frequency-domain signal vectors, thereby generating a combined filtered frequency-domain signal vector, transforming the combined filtered frequency-domain signal vector into the time domain, thereby generating a combined filtered time-domain signal vector, adapting the length of the combined filtered time-domain signal vector, and subtracting the adapted combined filtered time-domain signal vector from a received signal block generally corresponding in time to the transmitted signal block, thereby resulting in a received signal block from which NEXT has been at least partially cancelled.
In another aspect of the present invention the providing step may include tansforming the coefficients of the FIR filters into the frequency domain, thereby generating the frequency response vector per FIR filter.
In another aspect of the present invention the method may further include selecting a subset of the FIR filters associated with each of the modems and performing any of the steps on the subset of FIR filters.
In another aspect of the present invention any of the adapting steps may further include performing overlap add.
In another aspect of the present invention any of the adapting steps may further include performing overlap save.
In another aspect of the present invention the method may further include feeding back the signal block from which NEXT has been at least partially cancelled to at least one of the FIR filters for adaptation thereat.
In another aspect of the present invention the method may further include initializing the taps of any of the FIR filters.
In another aspect of the present invention any of the transforming steps may further include tansforming using FFT.
In another aspect of the present invention the method may further include feeding back the received signal block from which NEXT has been at least partially cancelled to at least one of the FIR filters and adjusting the FIR coefficients in accordance with the fed-back signal.
In another aspect of the present invention the adjusting step may further include adjusting using Least Mean Square (LMS) adaptation.
In another aspect of the present invention a NEXT cancellation system is provided in a modem pool including a plurality of modems, each modem transmitting a signal having a plurality of contiguous signal blocks at least one FIR filter operably connected to each of the modems, each FIR filter for filtering signals from a transmitting one of the modems, and each FIR filter having an associated frequency response vector, means for adapting the length of any of the signal blocks to equal the length of any of the frequency response vectors, means for transforming the adapted signal block into the frequency domain, thereby generating a frequency-domain signal vector, means for multiplying the frequency response vector of the FIR filter by a corresponding one of the frequency-domain signal vectors, thereby generating a altered frequency-domain signal vector, means for adding the filtered frequency-domain signal vectors, thereby generating a combined filtered frequency-domain signal vector, means for transforming the combined filtered frequency-domain signal vector into the time domain, thereby generating a combined filtered time-domain signal vector, means for adapting the length of the combined filtered time-domain signal vector, and means for subtracting the adapted combined filtered time-domain signal vector from a received signal block generally corresponding in time to the transmitted signal block, thereby resulting in a received signal block from which NEXT has been at least partially cancelled.
In another aspect of the present invention the system may further include means for transforming the coefficients of the FIR filters into the frequency domain, thereby generating the frequency response vector per FIR filter.
In another aspect of the present invention the system may further include means for selecting a subset of the FIR filters associated with each of the modems and where any of the means is operative to process the subset of FIR filters.
In another aspect of the present invention any of the adapting means may be operative to perform overlap add.
In another aspect of the present invention any of the adapting means may be operative to perform overlap save.
In another aspect of the present invention the system may further include means for feeding back the signal block from which NEXT has been at least partially cancelled to at least one of the FIR filters for adaptation thereat.
In another aspect of the present invention the system may further include means for initializing the taps of any of the FIR filters.
In another aspect of the present invention any of the transforming means may be operative to transform using FFT.
In another aspect of the present invention the system may further include means for feeding back the received signal block from which NEXT has been at least partially cancelled to at least one of the FIR filters and where the FIR filter is operative to adjust the FIR coefficients in accordance with the fed-back signal.
In another aspect of the present invention the FIR filter may be operative to adjust using Least Mean Square (LMS) adaptation.
The disclosures of all patents, patent applications, and other publications mentioned in this specification and of the patents, patent applications, and other publications cited therein are hereby incorporated by reference.